/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/number-of-distinct-islands
   @Language: C++
   @Datetime: 19-06-14 11:24
   */

class Solution {
	string bfs(vector<vector<int> > &grid, int r, int c){
		int rows=grid.size(), cols=grid[0].size(), row=r, col=c;
		int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
		queue<pair<int,int> > q;
		string str;
		for(q.push({r,c}); q.size(); q.pop()){
			r=q.front().first, c=q.front().second;
			if(r<0 || r>=rows || c<0 || c>=cols) continue;
			if(grid[r][c]==0) continue;
			grid[r][c]=0;
			str.append(to_string(r-row)+","+to_string(c-col)+";");
			for(int i=4; i--; q.push({r+dir[i][0],c+dir[i][1]}));
		}
		return str;
	}
public:
	/**
	 * @param grid: a list of lists of integers
	 * @return: return an integer, denote the number of distinct islands
	 */
	int numberofDistinctIslands(vector<vector<int> > &grid) {
		// write your code here
		unordered_set<string> islands;
		for(int i=0; i<grid.size(); ++i)
			for(int j=0; j<grid[i].size(); ++j)
				if(grid[i][j]){
					string island=bfs(grid,i,j);
					if(islands.count(island)==0) islands.insert(island);
				}
		return islands.size();
	}
};
